# -*- coding: utf-8 -*-
'''
@author: Ricardo Faria 6315 e Luís Freitas 5602
@date: 8 abril de 2013
Classe que permite criar um obtecto Quick
'''
class Quick:
    
    def __init__(self, A):
        '''
        Contrutor da classe Quick
    @   param A: Lista a receber
        '''
        self.A = A
    
    def quicksort(self, p, r):
        '''
        Método recursivo responsável pela ordenação final da lista.
        @param p: posicao inicial
        @param r: posicao final
        '''
        if p<r:
            q = self.partition(p, r)
            self.quicksort(p, q-1)
            self.quicksort(q+1, r)

    
    def partition(self, p, r):
        '''
        Metodo que efetua a particao do array
        @param p: Posicao inicial
        @param r: Posicao final
        '''
        x = self.A[r]
        i = p-1

        for j in range(p, r):
            if(self.A[j]<= x):
               i = i +1
               self.A[i], self.A[j] = self.A[j], self.A[i]
               
        self.A[i+1],self.A[r] = self.A[r],self.A[i+1]
        
        return i + 1
